I. Field of the Invention
The present invention relates generally to decoding in communication systems and, in particular, to the calculation of branch metrics in logMAP turbo decoding in wireless communication systems.
II. Description of the Related Art
Turbo decoding utilizes interactive decoding and random interleaving to achieve an error performance close to the Shannon limit Consequently, turbo decoding is often employed in decoding for third generation (3G) wireless communications systems.
A trellis diagram represents the possible state changes of a convolutional encoder over time. Each state in the trellis is connected, via two associated branch metrics, to two separate states in the trellis in the next time period. When decoding received symbols, decoding algorithms typically traverse the trellis in a forward direction to determine the probabilities of the individual states and the associated branch metrics.
The logMAP algorithm differs from other decoding algorithms, such as the Viterbi algorithm, by performing both a forward and a backward recursion over a trellis. The algorithm can be partitioned to provide a Windowed LogMAP arrangement where the blocks are divided into smaller alpha and beta recursions. Alpha values, representing the probabilities of each state in the trellis, are determined in the forward recursion. Beta values, representing the probabilities of each state in the reverse direction, are determined during the backwards recursion.
The respective probabilities of each pair of branch metrics associated with any given state are the gamma values (γ). The gamma values are calculated during each of the forward and backwards recursions of the trellis. The logMAP branch metrics are calculated using the following equation:γki=di(ys+Le)+ypci,k  (1)where i represents the path (0 or 1), d and c are the expected data and parity bits, respectively, and ys, yp and Le represent the soft information for data, parity and extrinsic information, respectively, and k represents the current state in the trellis for which branch metrics are being calculated.
For any given rate ½ trellis code, each of the expected data and parity bits, d and c respectively, may take the values of +1 or −1. Consequently, there are four possible branch metric combinations for the given input variables:                (ys+Le+yp) for d=+1, c=+1;        (ys+Le+yp) for d=+1, c=−1;        (−ys−Le−yp) for d=−1, c=−1;        (−ys−Le+yp) for d=−1, c=+1.        
When traversing the trellis in the forward recursion stage, both the input symbol and the extrinsic memory must be accessed to compute the gamma values. FIG. 1 shows a prior art arrangement 100 for calculating branch metrics for a rate ½ decoder. Data (ys) 130 and parity (yp) 140 are read from a first memory 120. The time and power required for read accesses from the first memory 120 are proportional to the size of the first memory 120. The first memory 120 must be sufficiently large to store data and parity information for the entire length of the block being decoded. The first memory 120 is typically of the order of −5 k words in size for mobile communications applications.
It is possible to store the data 130 and parity 140 in two distinct memory units, rather than the single first memory 120. However, there does not appear to be any apparent advantage associated with such an implementation, as reading the required data 130 and parity 140 from separate memory units would require two memory address decodes in addition to the retrieval of the information. Such an implementation is not appreciably faster than a single memory unit implementation and requires more power.
A processor 150 receives the data 130 and parity 140, along with extrinsic information (Le) 115 that is read from a second memory 110, to produce output branch metrics 155 corresponding to all paths in the trellis. The output branch metric 155 is presented to a trellis calculation module 160 that utilizes the output branch metric 155 to traverse the trellis.
When the backward recursion of the trellis commences to calculate the beta values, each of the four possible combinations for the branch metric computation must be regenerated. This requires a read access to the memory 120 storing data and parity information, and one read access to the second memory 110 storing extrinsic information, in addition to the cost of computation in the processor 150. As noted above, the time and power consumption of each memory access is directly proportional to the number of memory cells and, consequently, each read access to either one of the first memory 120 and the second memory 110 is costly with respect to power consumption. Therefore, reducing the number of read accesses to either one or both of the first memory 120 and the second memory 110 would be advantageous.
FIG. 2 shows a prior art arrangement 200 for calculating branch metrics for a rate ⅓ LogMAP decoder. The branch metric combinations are given by Equation 2 below, in which yp1 represents a first parity bit, yp2 represents a second parity bit, c1 represents the expected first parity bit and c2 represents the expected second parity bitγki=di(ys+Le)+yp1c1i,k+yp2c2i,k  (2)
As each of d, c1 and c2 can be either +1 or −1, there are eight possible branch metric combinations for a rate ⅓ decoder.
A first memory 220 stores each of data (ys) 230, first parity (yp1) 240 and second parity (yp2) 245. Each of the data (ys) 230, first parity (yp1) 240 and second parity (yp2) 245 is read from the first memory 220 and presented to a processor 250. The processor 250 also receives extrinsic information (Le) 215 that is read from a second memory 210. The processor 250 calculates all the branch metrics 255, and presents the branch metrics 255 to a trellis calculation module 260.
Branch metrics calculated during the forward recursion of a decoding trellis are often stored in memory units so that the branch metrics can be reused during a backwards recursion of the decoding trellis. As all of the branch metrics calculated during the forward recursion are stored, the memory units utilized are necessarily large. As noted above, read accesses to such memory units are costly in respect of power consumption and time.
In UMTS and CDMA 2000 systems, approximately 40% of computation in baseband processing is in the turbo decoding process alone. A single component can dominate the power consumption of a low-power handset, or a large infrastructure product. Any amount of power savings translates into a substantial advantage in the handset market, where battery life is paramount, or in packaging for wireless infrastructure products, where heat dissipation is important.